/**
 * CS340 Fatboy Mafia Team
 */
package fatboy.hypeerweb;

import java.io.Serializable;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;

import fatboy.addons.Visitor;
import fatboy.communication.ObjectID;
import fatboy.communication.ResidentDatabase;

import junit.framework.Assert;

/**
 * The Hypeerweb Node Class.  Stores an object, and methods to communicate with other nodes.
 * 
 * @author CS340 Fatboy Mafia Team - collaborative efforts
 * @domain 
 * 			A unique node identifier "address": a NodeAddress 
 * 			Neighboring nodes "neighbors": a set of zero or more unique node pointers, who's address differ from this node's by only one bit
 * 			Child node "child": zero or one neighbor, who's address is less than this node's
 * 			Parent node "parent": zero or one neighbor, who's address is greater than this node's
 * 			The fold node "fold": zero or one node pointer
 * 			Surrogate nodes "upDownPointers": a set of zero or more nodes.
 * 			Reverse-surrogate nodes "upDownPointers": a set of zero or more nodes.
 */
public class Node implements Comparable<Object>, Serializable {

	/* Turns debugging comments on and off. */
	//public boolean debug = false;
	
	private static final long serialVersionUID = -1773804910365317670L;

	/** Node State (for state pattern). */
	private NodeState nodeState;

	/** global id. */
	private ObjectID id;

	/** The State singletons. Each have one instance only. Instantiated at class load time */
	private static final NodeState interiorNodeState = new InteriorNodeState();
	private static final NodeState surfaceNodeState = new SurfaceNodeState();
	private static final NodeState edgeNodeState = new EdgeNodeState();
	private static final NodeState lastNodeState = new LastNodeState();
	private static final NodeState nullNodeState = new NullNodeState();

	/** The nullNode singleton. Represents a nonexistent node */
	static final Node nullNode = new Node(NodeType.NULL_NODE, true);

	static final int BOGUS = Integer.MAX_VALUE;

	/** The hyperweb address of the node. */
	private NodeAddress address;

	/** Collection of Edge/Surrogate pointers. */
	private PointerList upDownPointers;

	/** NeigbourPointers (PriorityQueue). */
	private PriorityQueue<Node> neighbors;

	/** FoldPointer (Node). */
	private Node foldPointer;

	/** Child(Node). */
	private Node child = nullNode;

	/** Parent (Node). */
	private Node parent;

	/** The data. */
	private Object data;
	
	/** The payload */
	private Payload payload;
	/**
	 * Instaniates the nullNode
	 * @pre type the incoming type must be nullNode Type
	 */
	public Node(final NodeType type, boolean nullN){
		if(type == NodeType.NULL_NODE){
			data = null;
		this.setAddress(new NodeAddress(BOGUS-1));
		setUpDownPointers(new PointerList());
		setNeighbors(new PriorityQueue<Node>());
		child =this;
		parent = this;
		foldPointer = this;
		setId(new ObjectID());
		ResidentDatabase.setObject(id, this);
		setNodeState(type);
		}
		else{
			throw new IllegalArgumentException();
		}
	}

	/**
	 * Instantiates a new node.
	 * @param o the data
	 * @param type the type of the node
	 * @param address the hyperweb address of the node
	 * @pre o, type, and address are not null
	 * @post returns a node that contains o with an address of address
	 * and the state corresponding to type
	 */
	public Node(Object o, final NodeType type, final NodeAddress address) {
		data = o;
		this.setAddress(address);
		setUpDownPointers(new PointerList());
		setNeighbors(new PriorityQueue<Node>());
		child = nullNode;
		parent = nullNode;

		setFoldPointer(this);
		setId(new ObjectID());
		setNodeState(type);

	}
	
	/**
	 * Instantiates a new node.
	 * @param o the data
	 * @param address the address of the node
	 * @pre o and address are not null
	 * @post returns a node that contains o with an address of address
	 * and is in an interior node state
	 */
	public Node(Object o, final NodeAddress address) {
		this(o, NodeType.INTERIOR_NODE, address);
	}

	/**
	 * a do nothing constructor for the proxy Node.
	 */
	public Node() {
		data = null;
		address = null;
		this.upDownPointers = null;
		setNeighbors(null);
		parent = null;
		foldPointer = null;
		id = null;
		nodeState = null;
	}
	public Node(int length) {
		this(length, NodeType.INTERIOR_NODE, new NodeAddress(length));
	}

	/**
	 * Gets the hypeerweb NodeAddress of the node.
	 * @return the Hypeerweb node address
	 * @pre true
	 * @post returns the node address for this node
	 */
	public NodeAddress getAddress() {
		return address;
	}

	/**
	 * Finds and returns the node at the destination.
	 * @param destination the address of the target node
	 * @return the node
	 * @pre there is a node with the address destination and destination is null
	 * @post returns the node with the address destination
	 */
	public Node getNodeAt(final NodeAddress destination) {
		if (getAddress().equals(destination)||destination== null) {
			return this;
		}
		//System.out.println("At:\n" + this+ "\nLooking for : "+destination);
		final Node neighborOnPath = getAddress().onPathTo(destination, 
				new PriorityQueue<Node>(this.getNeighbors()));
		if(neighborOnPath!=null){
			return neighborOnPath.getNodeAt(destination);
		}
		return neighborOnPath;
	}
	
	/**
	 * Hash code.
	 * @return the int
	 * @pre true
	 * @post returns a int that can be used to represent this Object
	 */
	public int hashCode() {
		return getAddress().hashCode();
	}

	/**
	 * Checks whether two nodes are the same by comparing their addresses (Web IDs).
	 * @param o - object passed
	 * @pre object passed is the instance of Node class
	 * @post returns false if the object passed is not the instance of Node class
	 * 	or if the address of the node passed is different from this node. Otherwise,
	 * 	returns true.
	 */
	public boolean equals(Object o){
		if(!(o instanceof Node)){
			return false;
		}
		Node n = (Node)o;
		return n.getAddress().equals(getAddress());
	}
	
	/**
	 * Compare to.
	 * @param o the o
	 * @return the int
	 * @pre o is an instance of Node class
	 * @post returns a -1 if o is greater than this, 0 if o is equal to this, 1 smaller than this
	 */
	public int compareTo(Object o) {
		Assert.assertTrue(o instanceof Node);
		return -1 * getAddress().compareTo(((Node) o).getAddress());
	}
	
	/**
	 * Gets this node's child.
	 * @return the child of this node
	 * @pre true
	 * @post returns the child of this node
	 */
	public Node getChild() {
		if (this == nullNode) {
			return nullNode;
		}
		return child;
	}
	
	/**
	 * Gets this node's parent.
	 * @return the parent of this node
	 * @pre true
	 * @post returns the parent of this node
	 */
	public Node getParent() {
		if (this == nullNode) {
			return nullNode;
		}
		return parent;
	}
	
	/**
	 * Gets the PriorityQueue of Neighbors.
	 * 
	 * @pre true
	 * @post returns the PriorityQueue of Neighbors
	 */
	public PriorityQueue<Node> getNeighbors() {
		return neighbors;
	}
	
	/**
	 * Sets Child to be the child of this node.
	 * 
	 * @param child the child
	 * 
	 * @pre child is not this node, is an edge node, and is a valid neighbor.  This node is a surface node.
	 * @post child is now this.child and this is an interior node
	 */
	public void setChild(Node child) {
		Assert.assertTrue(!this.equals(child));
		this.child = child;
	}
	
	/**
	 * For use with the add method.  Sets the childs and changes the state of this node to interior node.
	 * @param child
	 */
	public void setupChild(Node child) {
		Assert.assertTrue(child.getNodeType() == NodeType.EDGE_NODE);
		setChild(child);
		this.setNodeState(NodeType.INTERIOR_NODE);
	}
	
	/**
	 * Sets Parent to be the parent of this node.  Also sets this node to be the parents' child.
	 * 
	 * @param parent the parent
	 * 
	 * @pre parent is not this node and a valid parent of this Node
	 * @post parent is now this node's parent, and this is an edge node
	 */
	public void setParent(Node parent) {
		Assert.assertTrue(!this.equals(parent));
		this.parent = parent;
	//	System.out.println(parent);
	}
	
	/**
	 * For use with the add method.  Sets the parent and changes the node state of this node to Edge node
	 * @param parent
	 */
	public void setupParent(Node parent) {
		setParent(parent);
		this.setNodeState(NodeType.EDGE_NODE);

		if(parent.equals(nullNode)){
			return;
		}
		parent.setChild(this);
	}
	
	/**
	 * Adds the neighbor.
	 * 
	 * @param newNeighbor the new neighbor
	 * 
	 * @pre the new neighbor is a valid neighbor for this node
	 * @post the new neighbor is added, and the list of neighbors for this node is correct
	 */
	public void addNeighbor(Node newNeighbor) {
		Assert.assertTrue(getAddress().isValidNeighbor(newNeighbor.getAddress()));
		getNeighbors().add(newNeighbor);
		//Assert.assertTrue(neighborListIsCorrect());
	}
	
	/**
	 * Removes the neighbor.
	 * 
	 * @param neighbor the neighbor to be removed
	 * 
	 * @pre the neighbor is in this node's list of neighbors, and is a valid neighbor for this node
	 * @post the neighbor is removed, and the list of neighbors for this node is correct
	 */
	public void removeNeighbor(Node neighbor) {
		Assert.assertTrue(getNeighbors().contains(neighbor));
		//Assert.assertTrue(getAddress().isValidNeighbor(neighbor.getAddress()));
		getNeighbors().remove(neighbor);	
		Assert.assertTrue(neighborListIsCorrect());		
	}
	

	
	/**
	 * Removes the surrogate pointer at the specified index.
	 * If this removes the last surrogate pointer from this node, this node type
	 * changes to "Interior".
	 * 
	 * @param index the index
	 */
	public void removeSurrogatePointerAt(int index) {
		getPointers().remove(index);
		if (getPointers().size() == 0) {
			setNodeState(NodeType.INTERIOR_NODE);
		}
	}
		
	/**
	 * Removes the specified surrogate from the list of surrogate pointers.
	 * If this removes the last pointer from this node, this node type
	 * changes to "Interior".
	 * 
	 * @param surrogatePointer the surrogate pointer to remove from this node's surrogate-list
	 * 
	 * @pre this node is an edge node, surrogatePointer is a surrogate pointer
	 */
	public void removeSurrogatePointer(NodePointer surrogatePointer) {
		Assert.assertTrue(this.getNodeType() == NodeType.EDGE_NODE);
		Assert.assertTrue(surrogatePointer instanceof SurrogatePointer);
        Assert.assertTrue(getPointers().contains(surrogatePointer));
        
		removeSurrogatePointerAt(getPointers().indexOf(surrogatePointer));
	}

	/**
	 * Adds the surrogate pointer.
	 * If this adds the first surrogate pointer to this node,
	 * this node type changes to "Edge".
	 * 
	 * @param node the node to add as a pointer
	 */
	public void addSurrogate(Node node) {
		Assert.assertTrue(!this.equals(node));
		getPointers().add(new SurrogatePointer(node));
		setNodeState(NodeType.EDGE_NODE);
	}

	/**
	 * Removes the edge pointer at the specified index.
	 * If this removes the last edge pointer from this node, this node type
	 * changes to "Interior".
	 * 
	 * @param index the index
	 */
	public void removeEdgePointerAt(int index) {
		getPointers().remove(index);
		if (getPointers().size() == 0) {
			setNodeState(NodeType.INTERIOR_NODE);
		}
	}
	
	/**
	 * Removes the specified edge from the list of edge pointers.
	 * If this removes the last edge pointer from this node, this node type
	 * changes to "Interior".
	 * 
	 * @param edge the edge to remove from this node's edge-list
	 */
	public void removeEdgePointer(Node edge) {
		EdgePointer edgePointer = new EdgePointer(edge);
        Assert.assertTrue(getPointers().contains(edgePointer));
		removeEdgePointerAt(getPointers().indexOf(edgePointer));
	}

	/**
	 * Adds the edge pointer.
	 * If this adds the first edge pointer to this node,
	 * this node type changes to "Surface".
	 * 
	 * @param node the node to add as a pointer
	 */
	public void addEdgePointer(Node node) {
		Assert.assertTrue(!this.equals(node));
		getPointers().add(new EdgePointer(node));
		setNodeState(NodeType.SURFACE_NODE);
	}

	/**
	 * A handle to the upDownPointers.
	 * 
	 * @return the up/down pointers
	 * @pre true
	 * @post returns a list of pointers to all current surrogate or edge pointers
	 *    from this node.
	 */
	public PointerList getPointers() {
		return getUpDownPointers();
	}

	/**
	 * Gets the node type.
	 * 
	 * @return the node type
	 */
	public NodeType getNodeType() {
		return nodeState.getType();
	}

	/**
	 * Returns the fold of this node.
	 * 
	 * @return the fold of this node
	 */
	public Node getFold() {
		return getFoldPointer();
	}

	/**
	 * Gets the node state (singleton) object.
	 * 
	 * @return the node state
	 * @pre true
	 * @post returns the correct state of this node
	 */
	public NodeState getNodeState() {
		return nodeState;
	}

	/**
	 * Sets the node state.
	 * 
	 * @param state the new node state
	 * @pre state is a valid NodeType with a corresponding NodeState
	 * @post the state of this node is set to that specified by state
	 */
	public void setNodeState(NodeType state) {
		if (state == NodeType.INTERIOR_NODE) {
			nodeState = interiorNodeState;
		} else if (state == NodeType.EDGE_NODE) {
			nodeState = edgeNodeState;
		} else if (state == NodeType.SURFACE_NODE) {
			nodeState = surfaceNodeState;
		} else if (state == NodeType.LAST_NODE) {
			nodeState = lastNodeState;
		} else if (state == NodeType.NULL_NODE) {
			nodeState = nullNodeState;
		}
	}

	/**
	 * Called on a node to be removed, it breaks all neighbor ties and makes 
	 * them surrogates with it's parent, and the parent gets edge pointers for them
	 * @pre This Node has been prepared to be removed
	 * @post All of this Node neighbors no longer point to it, but have surrogate pointers
	 * for it's parent and the parent has an edge pointer to each of them
	 */
	 public void removeNeighbors(){
		for(Node neighbor : getNeighbors()){
			if(neighbor == getParent()){
				continue;
			}
			if(getParent() != nullNode){
				neighbor.addSurrogate(getParent());
				getParent().addEdgePointer(neighbor);
			}
			neighbor.removeNeighbor(this);

		}
		this.setNeighbors(new PriorityQueue<Node>());
		NodeAddress newChildAddress = null;
		if(!getParent().equals(nullNode)){
			getParent().removeNeighbor(this);
			newChildAddress = getAddress().getNextYoungestChild(getParent().getAddress());
		}
		if(newChildAddress == null){
			getParent().setChild(nullNode);
		}
		else{
			/*System.out.println("Getting new Child: "+newChildAddress); */
			getParent().setChild(getParent().getNodeAt(newChildAddress));
			//System.out.println("Got: "+ parent.child);
		}
		this.setParent(nullNode);
		this.setChild(nullNode);
	}
	 
	/**
	 * Disconnects this node from the hypeer web by removing its references to 
	 * 	its neighbors, including its parent and child.
	 * @pre true
	 * @post this node loses all the references it contains about its neighbors 
	 */
	 public void removeNeighbors2(){
			this.setNeighbors(new PriorityQueue<Node>());
			this.setParent(nullNode);
			this.setChild(nullNode);
		}
	/**
	 * Removes all the edge pointers pointing to this node, and all of this node's surrogate pointers.
	 * @pre this node is an edge node or a last node, and is the node to be detached and removed from the hypeerweb.
	 * @post all edge and surrogate pointers to and from this node are gone.
	 */
	public void removeSurrogates() {
		//Assert.assertTrue(this.getNodeType() == NodeType.EDGE_NODE || this.getNodeType() == NodeType.LAST_NODE);
			for (int i = getPointers().size() - 1; i >= 0; i--) {
				NodePointer pointer = getPointers().get(i);
				if(pointer.getClass() == SurrogatePointer.class){
					pointer.getNode().removeEdgePointer(this);				
					this.removeSurrogatePointer(pointer);
				}
				else{
					pointer.getNode().removeSurrogatePointer(new SurrogatePointer(this));
					this.removeEdgePointer(pointer.getNode());
				}
	        }
		Assert.assertTrue(getPointers().isEmpty());
	}

	
	/**
	 * Removes the node from the HypeerWeb
	 * @author James
	 * 
	 * @param nodeToRemove - node we are removing 
	 * @precondition nodeToRemove is in the tree
	 * @postcondition all worked and is valid
	 */
	public synchronized Node remove(Node nodeToRemove){ 
		//break a DB association
		
		Node removalPoint;
		Node insertionPoint = findInsertionPoint();
		if(insertionPoint.getAddress().getAddress()==0){
			removalPoint = insertionPoint.getFold();
		}
		else{
			removalPoint = this.getNodeAt(insertionPoint.getAddress().decrement()).getChild();
		
		}
		
		NodeAddress removedAddress = new NodeAddress(removalPoint.getAddress().getAddress());
		
		Node finder = this;
		if(nodeToRemove.equals(this)){
			finder = this.foldPointer;
		}
		removalPoint.removeFold();
		removalPoint.removeSurrogates();
		removalPoint.removeNeighbors();
		//End detachment
		
		if(!nodeToRemove.equals(removalPoint)){
			nodeToRemove.givePointersTo(removalPoint);
			nodeToRemove.removeFold2();
			nodeToRemove.removeSurrogates();
			nodeToRemove.removeNeighbors2();
		}
		
		else{
			removalPoint = this;
		}
		if(Integer.bitCount(removedAddress.getAddress()) == 1){
			
			Node last = finder.getNodeAt(new NodeAddress(removedAddress.getAddress()-1));
			last.setNodeState(NodeType.LAST_NODE);
		}

		//System.out.println(this);
		
		if(!this.equals(nodeToRemove)){
			this.nodeState.assertNodeStateIsCorrect(this);
		}
		if(removalPoint.getNeighbors().size() == 0){
			removalPoint.setFoldPointer(removalPoint);
		}
		removalPoint.getNodeState().assertNodeStateIsCorrect(removalPoint);
		nodeToRemove.setAddress(new NodeAddress(BOGUS));
		ResidentDatabase.remove(nodeToRemove.getId());
		
		return removalPoint;
	}
	/**
	 * called to relocate this node to the removal point and move it 
	 * to this Node's spot in the hypeerweb
	 * @param removalPoint node to switch pointers with me
	 * @pre hypeerweb is properly formed and removal point is not null
	 * @post this Node points to everything the removal point did,
	 *  and the removal Point points to everything this node did.
	 *  also everything that pointed to the removal node points to this node
	 *  and everything that pointed to this node points to the removal node
	 */
	public void givePointersTo(Node removalPoint) {
		NodeState oldState = this.nodeState;
		NodeAddress temp = getAddress();
		setAddress(removalPoint.getAddress());
		removalPoint.setAddress(temp);
		giveNeighbors(removalPoint);
		for(Node neighbor : getNeighbors()){
			neighbor.removeNeighbor(this);
		}
		removalPoint.foldPointer = this.foldPointer;
		if(	this == foldPointer.foldPointer){
			foldPointer.foldPointer = removalPoint;	
		}
		//System.out.println(removalPoint.address + " " + address);
		if(removalPoint.getAddress().hasOldFold(getAddress())){
			//System.out.println("here1");
			Node oldFold = removalPoint.getNodeAt(removalPoint.getAddress().computeOldFold());
			if(oldFold.foldPointer == this){
				oldFold.foldPointer = removalPoint;
				//System.out.println("here2");
			}
		}
		//swappingPointers
		givePointers(removalPoint);
		
		giveParentChild(removalPoint);
		removalPoint.setNodeState(oldState.getType());
	}
	
	/**
	 * Changes the parent and the child of the passed node (removalPoint) to the
	 *	parent and the child of this node. Updates a child pointer of the parent
	 *	and parent pointers of the children of this node to point to the
	 *	removal point. 
	 * @param removalPoint
	 * @pre this node's child and parent pointer are set according to the rules 
	 * 	of the hypeerweb, removalPoint is a node with a valid 
	 * 	address in the hypeerweb
	 * @post the parent and children of this node is now point to removalPoint and
	 * 	removalPoint is now points to the children and the parent of this node
	 */
	public void giveParentChild(Node removalPoint) {
		removalPoint.setParent(parent);
		removalPoint.setChild(child);
		
		// if necessary, update the child pointer of the parent of this node
		//to point at the insertion point
		if(getParent().getChild() == this){
			getParent().setChild(removalPoint);
		}
		
		//update the parent pointer of the children nodes of this node, if any
		List<NodeAddress> possibleChildren = removalPoint.getAddress().getAllPossibleChildren(
				this.getAddress());
		for(NodeAddress n: possibleChildren){
			
			Node possible = removalPoint.getNodeAt(n);
			//System.out.println("Node: " +possible + " was from address: " + n);
			if(possible.getParent().equals(this)){
				possible.setParent(removalPoint);
			}
		}
	}

	/**
	 * Places Edge or Surrogate pointers of this node in the node passed (removalPoint)
	 * @param removalPoint - the node that is going to substitute the node we are
	 * 	trying to remove
	 * @pre edge and surrogate pointers from and to this node are set properly
	 * 	(according to the rules of the hypeerweb), removalPoint is a node with a valid
	 * 	address in the hypeerweb
	 * @post edge or surrogate pointers of this node are now belong to the removalPoint and
	 * 	node that were pointing to this node are now pointing to the removal point 
	 */
	public void givePointers(Node removalPoint) {
		removalPoint.getUpDownPointers().clear();
		for(NodePointer np : this.getUpDownPointers()){
			if(np.getClass() == SurrogatePointer.class){
				//remember to remove edge pointers from np to this node
				np.getNode().addEdgePointer(removalPoint);
				removalPoint.addSurrogate(np.getNode());
			}
			else{
				//remember to remove surrogate pointers from np to this node
				np.getNode().addSurrogate(removalPoint);
				removalPoint.addEdgePointer(np.getNode());
			}
		}
	}

	/**
	 * Adds the neighbors of this node to the node passed (removalPoint) and adds the
	 * 	removalPoint as a neighbor to each of the neighbors of this node
	 * @param removalPoint
	 * @pre the neighbors of this node are correctly pointing to this node as a
	 *  neighbor and this node points correctly to all of its neighbors,
	 *  removalPoint is a node with a valid address in the hypeerweb
	 * @post the neighbors of this node are now recognizing the removalPoint as a
	 *  neighbor and the removalPoint has as neighbors all the neighbors of this node
	 */
	public void giveNeighbors(Node removalPoint) {
		//System.out.println(removalPoint);
		for(Node n : getNeighbors()){
			n.refreshNeighbors();
			n.addNeighbor(removalPoint);
			removalPoint.addNeighbor(n);
		}
	}

	/**
	 * Refreshes the priority queue of neighbors of this node so all the neighbors
	 *  become sorted in the queue from the lowest address to the highest address
	 *  after the node at the removal point replaces the removed node in the hypeerweb
	 *  @pre true
	 *  @post all the neighbors of this node are getting sorted based on their address
	 */
	public void refreshNeighbors() {
		setNeighbors(new PriorityQueue<Node>((Collection<Node>) getNeighbors()));
	}

	/**
	 * takes care of the fold pointer during the remove method
	 * @pre the hypeerweb is properly formed.  This node has a valid parent and a valid fold.
	 * @post my fold's fold is now my parent or my fold is null if I am the last node
	 */
	public void removeFold() {

		Assert.assertTrue(getParent() != null);
		Assert.assertTrue(foldPointer != null);
		//find the fold of the nodeToRemove and calculate the new fold for it
		// if the fold pointer of our node is not the first node in the HypeerWeb
		
		getFoldPointer().setFoldPointer(getParent());
		
		setFoldPointer(nullNode);
	}
	
	/**
	 * Disconects the fold pointer of this node from the hypeerweb
	 * @pre true
	 * @post the fold pointer of this node doesn't point to any of the nodes in the hypeerweb
	 */
	public void removeFold2() {
		Assert.assertTrue(foldPointer != null);
		//find the fold of the nodeToRemove and calculate the new fold for it
		// if the fold pointer of our node is not the first node in the HypeerWeb
		//foldPointer.foldPointer = parent;
		setFoldPointer(nullNode);
	}
	/**
	 * Gets the maximum neighbor.
	 * @pre the hypeerweb is properly formed. The neighbors of this node are properly sorted.
	 * @post returns the maximum neighbor of this node
	 */
	public Node getMaximumNeighbor() {
		return getNeighbors().element();
	}

	/**
	 * from edge pointers addresses and neighbors address of the Parent
	 * calculates the future surrogate addresses of new Child.
	 * 
	 * @param edgePointers edgePointer's addresses of Parent
	 * @param neighborsIn neighbor's addresses
	 * 
	 * @pre the hypeerweb is properly formed. The neighbors of this node are properly sorted.
	 * @post returns collection containing the nodes that should be surrogate pointers
	 * for the child
	 */
	public Set<Node> futureSurrogates(Collection<NodePointer> edgePointers,
			Collection<Node> neighborsIn) {
		final Set<Node> retSetTemp = new HashSet<Node>(neighborsIn);
		//System.out.println(edgePointers);
		for (NodePointer edgePointer : edgePointers) {
			retSetTemp.remove(edgePointer.getNode().getParent());
		}
		retSetTemp.remove(this);
		return retSetTemp;
	}


	/**
	 * Finds a pointer to the first childless surface node. That is, the node
	 * who's address is one greater than the node with the greatest address
	 * among nodes with EdgeNode childs.
	 * 
	 * @param lowerBound the node which acts as the lower bound of the search.
	 * @param upperBound must be a edge node or childless surface node. This node acts
	 * as the upper bound of the search.
	 * 
	 * @pre thehyperweb is set up correctly. lowerBound is an interiorNode or surfaceNode, with an edge child; or, the insertion point.  
	 *        upperBound is a edge or surface node with no edge child
	 * 
	 * @post returns the node which is the first (lowest) childless node (has no edge node child) in the range.  
	 *         returns the upperBound if the nodes are equal
	 */
	public Node findFirstChildlessInRange(Node lowerBound, Node upperBound) {
		Assert.assertNotNull(lowerBound);
		Assert.assertNotNull(upperBound);
		Assert.assertTrue(lowerBound.getNodeType() != NodeType.EDGE_NODE);
		Assert.assertTrue(upperBound.getChild().getNodeType() != NodeType.EDGE_NODE);
		
		if (lowerBound.getAddress().compareTo(upperBound.getAddress()) >= 0) {  
			//Assert.assertTrue(upperBound.getNodeType() != NodeType.EDGE_NODE);
			return upperBound;
		}

		final NodeAddress midpointAddress = NodeAddress.midPoint(lowerBound.getAddress(),
				upperBound.getAddress());
		final Node midpointNode = getNodeAt(midpointAddress);
		
		if (midpointNode.getNodeState().hasEdgeChild(midpointNode)) {
			lowerBound = getNodeAt(midpointNode.getAddress().addOne());
		} 
		else {
			upperBound = getNodeAt(midpointNode.getAddress());
		}
		
		return midpointNode.findFirstChildlessInRange(lowerBound, upperBound);
	}
	
	/**
	 * White box testing for findFirstChildlessInRange
	 * Tests the method on every size hypercube up to 66, and tests for every possible valid value of lowerBound and upperBound, 
	 * which tests valid BOUNDARY values (valid near-boundary values, and values at the boundaries). 
	 * This has full STATEMENT COVERAGE, and full BRANCH COVERAGE (excepting assertions).  
	 * It tests the few DEFINITION-USE cases. 
	 * It tests every state of the hyperweb, including a completed state.
	 * This tests recursive LOOPS by testing multiple levels of recursive iteration, including skipping recursion, one recursion, 
	 * two recursions, and more.
	 * 
	 */
	public static void testFindFirstChildlessInRange() {		
		final int LIMIT = 66;
		for (int max = 1; max < LIMIT; max++) {
			Connection web = new Connection();
			web.addNode(0);
			List<Node> nodeList = web.getAllNodes();
			int cubeSize = 1;
			
			for (int i = 1; i < max; i++) {
				Node added = web.addNode(i);	
				nodeList.add(added);
				cubeSize++;
			}	
			
			for (int lowerBound = 0; lowerBound < cubeSize; lowerBound++) {
				for (int upperBound = 0; upperBound < cubeSize; upperBound++) {
					Node lower = nodeList.get(lowerBound);
					Node upper = nodeList.get(upperBound);
					if (lower.getNodeType() != NodeType.EDGE_NODE && lower.getChild().getNodeType() == NodeType.EDGE_NODE) {
						if(upper.getChild().getNodeType() != NodeType.EDGE_NODE) {
							Node result = lower.findFirstChildlessInRange(lower, upper);						
							if (upperBound <= lowerBound) {
								Assert.assertEquals(upper, result);
							}
							Assert.assertTrue(result.getNodeType() != NodeType.EDGE_NODE);
						}
					}
				}
			}			
		}
	}

	/**
	 * Find insertion point.
	 * @pre the hypeerweb is properly formed.
	 * @post returns the node who will become the parent of the next added node. That
	 * is, the surface node with the lowest address among childless
	 * surface nodes.
	 */
	public Node findInsertionPoint() {
		return nodeState.findInsertionPoint(this);
	}
	
	/**
	 * Adds a new node to the hypeerweb containing the specified data.
	 * 
	 * @pre up to this point, hypeerweb is properly formed.
	 * @post adds the specified data (the object passed) to the hypeerweb
	 *  and returns the reference to the added node
	 * @param o the data to place in the new node
	 * @return a handle to the new node
	 * @throws IllegalAggumentException 	 
	 */
	public synchronized Node add(Node o) {
		Assert.assertNotNull(o);			

		final Node insertionPoint = findInsertionPoint();
		
		final NodeAddress edgePointerAddress = insertionPoint.getNodeState()
				.getFirstUpDownNodeAddress(insertionPoint);
		NodeAddress childAddress = null;

		// special case - setting the first node in the HypeerWeb to the Last Node state
		if (NodeAddress.asInt(insertionPoint.getAddress()) == 0) {
			childAddress = insertionPoint.getFoldPointer().getAddress().addOne();
			insertionPoint.getFoldPointer().setNodeState(NodeType.INTERIOR_NODE);
		} 
		else {
			childAddress = insertionPoint.getAddress().getChild(edgePointerAddress);
		}
		Assert.assertTrue(!childAddress.equals(this.getAddress()));
		o.setAddress(childAddress);
		final Node newChild = o; 
			
		Assert.assertTrue(!newChild.equals(insertionPoint));
		newChild.addOnto(insertionPoint);		
			
		Assert.assertTrue(insertionPoint.getChild().equals(newChild));
		insertionPoint.getNodeState().assertNodeStateIsCorrect(insertionPoint);
		newChild.getNodeState().assertNodeStateIsCorrect(newChild);
		
		return newChild;
	}

	/**
	 * Re-arranges all the up/down pointers of the new node and it's parent. All
	 * up (edge) pointers of the new parent are broken. All surrogate pointers
	 * of edge nodes which point to the new parent become neighbor pointers to
	 * the new child (this) instead. The new child's (this's) new neighbors are
	 * these same edge nodes.
	 * 
	 * @param insertionPoint the insertion point
	 * @pre insertionPoint is a valid node, hypeerweb is properly formed up
	 *  to this point
	 * @post this node is added as a child on to the insertion point node,
	 * 	pointers in the hypeerweb reset according to the rules of the hypeerweb
	 * @return true, if adds the onto
	 */
	public boolean addOnto(Node insertionPoint) {

		this.setupParent(insertionPoint);
		this.addNeighbor(insertionPoint);
		insertionPoint.setupChild(this);
		insertionPoint.addNeighbor(this);
		addFold();
		
		final Set<Node> surrogates = 
			futureSurrogates(insertionPoint.getPointers(), 
					new java.util.PriorityQueue<Node>(insertionPoint.getNeighbors()));
		final int numberOfUpPointers = insertionPoint.getPointers().size();
		for (int i = 0; i < numberOfUpPointers; i++) {
			final Node edgePointee = insertionPoint.getPointers().get(0).getNode();
			for (int j = 0; j < edgePointee.getPointers().size(); j++) {
				final Node edgeToSurrogatePointee = edgePointee.getPointers().get(j)
						.getNode();
				if (edgeToSurrogatePointee.equals(insertionPoint)) {
					edgePointee.removeSurrogatePointerAt(j);
				}
			}
			this.addNeighbor(edgePointee);
			edgePointee.addNeighbor(this);
			insertionPoint.removeEdgePointerAt(0);
		}
		for (Node n : surrogates) {
			addSurrogate(n);
			n.addEdgePointer(this);
		}
		if (getPointers().size() == 0) {
			this.setNodeState(NodeType.LAST_NODE);
		}

		return true;
	}

	/**
	 * Takes care of the fold pointer during an add.
	 * @pre hypeerweb is formed properly up to this point
	 * @post calculated fold pointer is properly set after the node
	 * 	is added to the hypeerweb
	 */
	public void addFold() {
		int foldAddress = NodeAddress.asInt(getAddress())^
				2*Integer.highestOneBit(NodeAddress.asInt(getAddress()))-1;
		if(foldAddress < 0){
			foldAddress *=-1;
		}
		setFoldPointer(getNodeAt(new NodeAddress(foldAddress)));
		getFoldPointer().setFoldPointer(this);
	}
	
	/**
	 * Accepts a visitor, which visits this node
	 * 
	 * @param visitor the visitor
	 * @param info the data needed by the visitor (such as a command, or a node pointer)
	 * 
	 * @pre true
	 * @return true, if successful
	 */
	public boolean accept(Visitor visitor, Object info) {
		System.out.println("Receiving "+visitor.getClass().getSimpleName()+" at " + address +".");
		visitor.visit(this,info);
		return true;
	}

	/**
	 * Simple to String method.
	 * 
	 * @pre true
	 * @post the string containing readable description of this node and its state
	 */
	public String toString() {
		String output = "Node: " + getAddress() 
						+ "\n\tNeighbors: [";
		final Node[] tempArr = getNeighbors()
				.toArray(new Node[getNeighbors().size()]);
		for (int i = 0; i < getNeighbors().size(); i++) {
			output += tempArr[i].getAddress().toString();
			if (i < getNeighbors().size() - 1){
				output += ", ";
			}
		}
		output += "]\n" + "\tFold: " + getFoldPointer().getAddress().toString() + "\n\t"
				+ getUpDownPointers().toString() + "\n\tData: " + data + "\n\t";
//				+ "Child: " + getChild().getAddress() + "\n\t"
//				+ "Parent: " + getParent().getAddress() + "\n\t";
//		output += getNodeType() + "\n\t";
		output += "ObjID: " + id + "\n";
		return output;
	}

	/**
	 * Sets the fold pointer.
	 * 
	 * @param foldPointer the new fold pointer
	 * @pre a valid node object should be passed as an argument
	 * @post the passed node is assigned as a fold pointer of this node
	 */
	public void setFoldPointer(Node foldPointer) {
		this.foldPointer = foldPointer;
	}

	/**
	 * Gets the fold pointer.
	 * 
	 * @pre true
	 * @post the fold pointer of this node
	 */
	public Node getFoldPointer() {
		return foldPointer;
	}
	

	
	/**
	 * Checks that the list of neighbors for this node is a valid list of neighbors.
	 *   Does not catch every case.
	 * 
	 * @pre the maximum neighbor for this node is correct
	 * @post returns true if this node has no invalid neighbors, 
	 *   and has all needed neighbors that are smaller than this node
	 */
	public boolean neighborListIsCorrect() {
		if (this.getAddress().getAddress() == 0 && getNeighbors().isEmpty()) {
			return true;
		}
		
		NodeAddress max = getMaximumNeighbor().getAddress();
		int thisDimention = Integer.highestOneBit(this.getAddress().getAddress());
		int neighborDimention = Integer.highestOneBit(max.getAddress());
		int dimention = Math.max(thisDimention, neighborDimention);
		
		int bitSum = 0;
		for (Node neighbor : getNeighbors()) {
			NodeAddress neighborAddress = neighbor.getAddress(); 
			Assert.assertFalse("*** this node has an invalid neighbor(s)", !this.getAddress().isValidNeighbor(neighborAddress)); 			
			NodeAddress bitDifference = this.getAddress().XOR(neighborAddress);
			bitSum += bitDifference.getAddress();			
		}
		
		Assert.assertFalse("*** this node doesn't have all appropriate neighbors", bitSum < dimention);
		return true;
	}

	public void setAddress(NodeAddress address) {
		this.address = address;
	}

	public void setUpDownPointers(PointerList upDownPointers) {
		this.upDownPointers = upDownPointers;
	}

	public PointerList getUpDownPointers() {
		return upDownPointers;
	}

	public void setId(ObjectID id) {
		this.id = id;
	}

	public ObjectID getId() {
		return id;
	}
	public Object writeReplace(){
		return new ProxyNode(id);
	}

	private void setNeighbors(PriorityQueue<Node> neighbors) {
		this.neighbors = neighbors;
	}

}

